import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-05-24
 * Time: 18:15
 */
public class TestHeap {
    public int elem[];
    public int UsedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 创建大根堆
     * @param array
     */
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            UsedSize++;
        }

        for(int i = (UsedSize-1-1)/2;i >=0;i--) {
            shiftDown(i);
        }
    }

    public void shiftDown(int parent) {
        int index = parent * 2 + 1;

        while (index < UsedSize) {
            if (index != UsedSize-1 && elem[index] < elem[index + 1]) {
                index++;
            }

            if (elem[index] > elem[parent]) {
                int tmp = elem[index];
                elem[index] = elem[parent];
                elem[parent] = tmp;
                parent = index;
                index = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,elem.length*2);
        }

        elem[UsedSize] = val;
        shiftUp(UsedSize);
        UsedSize++;
    }

    public void shiftUp(int child) {
        int parent = (child-1)/2;

        while(parent >= 0) {

            if(elem[parent] < elem[child]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1 )/2;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        return this.UsedSize == elem.length;
    }

    public int pollHeap() {
        if(empty()) {
            System.out.println("优先级队列为空");
            return -1;
        }

        int tmp = elem[0];
        elem[0] = elem[UsedSize-1];
        elem[UsedSize-1] = tmp;
        UsedSize--;
        shiftDown(0);
        return tmp;
    }

    public boolean empty() {
        return this.UsedSize == 0;
    }

    public int peekHeap() {
        if(empty()) {
            System.out.println("优先级队列为空！");
            return -1;
        }

        return elem[0];
    }
}
